package algorithmic_data_structure.动态规划;

import utils.PrintUtil;

public class 背包问题 {
    public static int maxValue(int[] w, int[] v, int bag){

//        return process(w,v,0,bag);
        return DPprocess(w,v,bag);
    }

    private static int process(int[] w, int[] v, int index, int rest) {
        if (index == v.length){
            return 0;
        }
//        if (rest < 0){
//            return -1;
//        }
        int p1 = process(w,v,index + 1,rest);
        int p2 = 0;
        if (rest >= w[index]){
            p2 = v[index] + process(w,v,index+1,rest-w[index]);
        }
        return Math.max(p1,p2);
    }
    private static int DPprocess(int[] w,int[] v,int bag){
        int[][] dp = new int[w.length+1][bag + 1];
        //设置边界值，可以省掉很多判断
//        for (int i = 0; i < bag + 1; i++) {
//            dp[w.length][i] = 0;
//        }
//        for (int i = 0; i < w.length; i++) {
//            dp[i][0] = 0;
//        }
        for (int index = w.length-1; index >= 0; index--) {
            for (int rest = w[index]; rest <= bag; rest++) {
                dp[index][rest] = Math.max(dp[index+1][rest],dp[index+1][rest-w[index]] + v[index]);
            }
        }
        PrintUtil.printArray(dp);
        return dp[0][bag];
    }
}
